package com.shu.Algorithm;

import java.util.*;

/**
 * @author ssm
 * @version V1.0
 * @description: 一致性hash算法思路：hash算法（CRC32_hash,FNV1_32_HASH,KETAMA_HASHD等）
 * @date 2020/8/17 14:33
 */

public class ConsistenceHash {

    // 物理节点集合
    private List<String> realNodes = new ArrayList<>();
    // 虚拟节点数，用户指定
    private int viretalNums = 100;
    // 物理节点与虚拟节点的对应关系存储
    private Map<String, List<Integer>> real2VirtualMap = new HashMap<>();
    // 排序存储结构红黑树，key是虚拟节点的hash值，value是物理节点
    private SortedMap<Long, String> sortedMap = new TreeMap<>();

    public ConsistenceHash(int viretalNums) {
        super();
        this.viretalNums = viretalNums;
    }

    public ConsistenceHash() {
        super();
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        ConsistenceHash consistenceHash = new ConsistenceHash();
        consistenceHash.addService("193.168.1.10");
        consistenceHash.addService("193.168.1.11");
        consistenceHash.addService("193.168.1.12");
        for (int i = 0; i < 100; i++) {
            System.out.println("a" + i + " 对应的服务器：" + consistenceHash.getService("a" + i));
        }


        SortedMap<Integer, String> testMap = new TreeMap<>();
        testMap.put(1, "a1");
        testMap.put(2, "a2");
        testMap.put(4, "a4");
        testMap.put(3, "a3");
        testMap.put(17, "a3");
        testMap.put(37, "a3");
        System.out.println(testMap);
        System.out.println(((TreeMap) testMap).tailMap(2));
        System.out.println(((TreeMap) testMap).headMap(2));
    }

    /**
     * 添加物理节点
     *
     * @param node
     */
    public void addService(String node) {
        String vnode = null;
        int i = 0;
        for (int count = 0; count < viretalNums; ) {
            i++;
            vnode = node + "#" + i;
            long hashValue = FNV1_32_HASH.hash(vnode);
            if (!this.sortedMap.containsKey(hashValue)) {
                count++;
                this.sortedMap.put(hashValue, node);
            }
        }
        this.realNodes.add(node);
    }

    /**
     * 删除物理节点
     *
     * @param node
     */
    public void removeService(String node) {
        for (int i = 0; i < viretalNums; i++) {
            sortedMap.remove(FNV1_32_HASH.hash(node.toString() + i));
        }
    }

    /**
     * 获取数据的存取节点
     *
     * @param key
     * @return
     */
    public String getService(String key) {
        long hash = FNV1_32_HASH.hash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Long, String> map = this.sortedMap.tailMap(hash);
        if (map.isEmpty()) {
            // 第一个Key就是顺时针过去离node最近的那个结点
            return this.sortedMap.get(sortedMap.firstKey());
        } else {
            return map.get(map.firstKey());
        }
    }

    /**
     * 计算Hash值, 使用FNV1_32_HASH算法
     */
    static class FNV1_32_HASH {
        /**
         * FNV1_32_HASH 算法
         *
         * @param target
         * @return
         */
        public static long hash(String target) {
            int p = 1677619;
            //使用Long类型
            Long hash = 2166136261L;
            char[] charArray = target.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                hash = (hash ^ charArray[i]) * p;
            }
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            if (hash < 0) {
                hash = Math.abs(hash);
            }
            return hash;
        }
    }

}
